#include<iostream>
#include "util.h"
using namespace std;

// algorithm for two arrays
// order statistics and meidan
// @desc get median from two sorted arrays
int getmedian(int* p1, int size1, int *p2, int size2){
  return 0;
}


// integer division is floor
// @time complexity: O(lgN)
// 4 10 20 30 40, 1 15 25 45 90
// 20 30 40, 1 15 25
// 20 30, 15 25 - special case
// 20, 25
// 20
double median(int * a, int * b, int n){
	printarray(a,0,n);
	printarray(b,0,n);
	if(n == 1)
		return a[0]<b[0] ? a[0] : b[0];
		//return (a[0] + b[0])/2.;
	int p=(n-1)/2;
	cout << a[p] << "\t" << b[p] << endl;
	if(a[p] == b[p])
		return a[p];
	else if(a[p] < b[p])
		return median(a+n/2, b, (n+1)/2);
	else
		return median(a, b+n/2, (n+1)/2);
}

void testmedian(){
	//int a[]={1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49,\
	52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94, 97};//{0,10,20,30};
	//int b[]={30, 34, 38, 42, 46, 50, 54, 58, 62, 66, 70, 74, 78, 82, 86, 90, \
		94, 98, 102, 106, 110, 114, 118, 122, 126, 130, 134, 138, 142, 146, 150, 154, 158};//{17,25,90,100};
	//int a[] = {4, 10, 20, 30, 40};
	//int b[] = {1, 15, 25, 45, 90};

	int a[] = {1,2,3,6,8};
	int b[] = {6,7,8,9,10};
	cout<<median(a, b, sizeof(a)/sizeof(int))<<endl;
}